package leetcode;

public class ArrangingCoins {

	public static void main(String[] args) {
		ArrangingCoins object = new ArrangingCoins();
		System.out.println(object.arrangeCoins(1804289383));
	}
	
	public int arrangeCoins(int n) {
		// 感觉这是一道数学题啊
		if (n <= 1) {
			return n;
		}
		// 求m^2 + m <= 2 * n的最大m
		long left = 1;
		long right = n;
		long middle = 0;
		while (left < right) {
			if (left == right - 1) {
				break;
			}
			middle = left + (right - left) / 2;
			//这里可能导致溢出
			if (middle * (middle + 1) <= 2L * n) {
				System.out.println("middle: " + middle);
				left = middle;
			} else {
				System.out.println("more than: middle" + middle);
				right = middle;
			}
		}
		System.out.println(right + "  " + left);
		return right * (right + 1) <= 2L * n ? (int)right : (int)left;
		
		//还可以使用求根公式来求解m^2 + m - 2 * n <= 0
		//x = ((-b ± √(b^ 2 + 4ac)) / 2a )
//		return (int)((-1 + Math.sqrt(1 + 8L * n)) / 2);
	}
}
